package offerbook;


import utils.TreeNode;

/**
 * Created at 2019/11/1 0001 上午 9:13
 * 判断是否是平衡二叉树：任何子树的左右孩子高度不能大于1。
 *
 * 方法1：遍历所有节点，每遍历一个节点，就判断当前节点是否平衡。
 *      做了许多重复工作，在遍历根节点的时候，明明可以通过左右孩子的信息就得出结论，这种方式
 *      会把前面做的工作给忽视掉。见方法二。
 *      本质原因是由上到下判断。
 *
 * 方法2：遍历所所有节点,每遍历一个节点，只要结合其左右孩子的信息来判断是否是平衡二叉即可。
 *      可以包装一个节点，每个节点都有高度和是否平衡，也可以把高度设定为全局变量，返回值只是boolean
 *      本质原因是由下到上判断。
 */
public class Code39_IsBalanceTree {

    /**
     * 方式1：先序遍历树，每遍历一个节点，就拿左右孩子高度判断
     */
    public boolean isBalanceTree(TreeNode root){
        if(root == null){
            return true;
        }
        if(Math.abs(getLevel(root.left) - getLevel(root.right)) > 1){
            return false;
        }
        return isBalanceTree(root.left) && isBalanceTree(root.right);
    }

    private static int getLevel(TreeNode root) {
        //叶子节点所在的层级
        if(root == null){
            return 0;
        }
        //当前树的高度是 左右孩子最大的高度 + 1
        return Math.max(getLevel(root.left),getLevel(root.right))+1;
    }


    private static class WarpNode{
        private int height;
        private boolean isBalance;
        public WarpNode(int height, boolean isBalance) {
            this.height = height;
            this.isBalance = isBalance;
        }
    }

    /**
     * 方式2：根据左孩子和右孩子的信息，直接判断。
     */
    public boolean isBalanceTree1(TreeNode root){
        if(root == null){
            return true;
        }
        return process(root).isBalance ;
    }

    private WarpNode process(TreeNode root) {
        if(root == null){
            return new WarpNode(0,true);
        }
        WarpNode left = process(root.left);
        //左子树是否平衡
        if(!left.isBalance){
            return new WarpNode(-1,false);
        }
        WarpNode right = process(root.right);
        //右子树是否平衡
        if(!right.isBalance){
            return new WarpNode(-1,false);
        }
        //当前数是否平衡
        //注意：虽然这三个条件可以写在一起，但是这样会导致递归的次数增加。分开写是过早的判断，减少递归次数
        if(Math.abs(left.height - right.height) >1){
            return new WarpNode(-1,false);
        }
        //否则平衡
        return new WarpNode(Math.max(left.height,right.height)+1,true);
    }
}
